package com.example.leetcode;

/**
 * 动态规划  ** 参考题解 ** 难点
 * 删除并获得点数
 */
public class Demo0740 {

    /**
     * 获取最大值，
     * 以元素为下标，以元素和为值(获取每个元素的和数组)
     * 无下标时无须担心为0
     * @param nums
     * @return
     */
    public int deleteAndEarn(int[] nums) {
        int max=0;
        for (int num : nums) {
            max=Math.max(num,max);
        }
        int[] sum=new int[max+1];
        for (int num : nums) {
            sum[num]+=num;
        }

        int[] fun=new int[max+1];
        fun[0]=sum[0];
        fun[1]=Math.max(sum[0],sum[1]);
        for (int i = 2; i < max+1; i++) {
            fun[i]=Math.max(fun[i-1],fun[i-2]+sum[i]);
        }
        return fun[max];
    }
}
